function [RC,A_sorted]=find_inv_pair(A)
%find_inv_pair.m
%A is a matrix of Nx1,RC is the num of inversion pair
tic;
[RC,A_sorted]=sort_and_count(A);
toc
end
function [RC,A_sorted]=sort_and_count(A)
A_size=size(A);
% if A is not a matrix of Nx1, reshape it
if A_size(2)>1
    A=reshape(A,[],1);
    A_size=size(A);
end
%if A is a number, return it
if A_size(1)==1
    A_sorted=A;
    RC=uint16(0);
    return;
end
%devide it and then conquer
L_size=A_size(1)/2;
A_left=A(1:L_size,1);
A_right=A(L_size+1:A_size,1);
%recursion, 
[RC_left,A_left]=sort_and_count(A_left);
[RC_right,A_right]=sort_and_count(A_right);
%combine
[C,A_sorted]=merge_and_count(A_left,A_right);

RC=RC_left+RC_right+C;
%A_sorted=A_sorted
end
function [RC,A_sorted]=merge_and_count(L,R)
L_size=size(L);
R_size=size(R);
%give a integar
k=1;
RC=uint16(k)-1;
index1=uint16(k),index2=uint16(k),k=uint16(k);
A_sorted=zeros(L_size(1)+R_size(1),1);
for k=1:L_size(1)+R_size(1)
    if index1>L_size(1)
         A_sorted(k,1)=R(index2,1);
        index2=index2+1;
    else if index2>R_size(1)
            A_sorted(k,1)=L(index1,1);
            index1=index1+1;
            RC = RC + L_size(1)-index1+1;
        else if L(index1,1)>R(index2,1)
                A_sorted(k,1)=R(index2,1);
                index2=index2+1;
                RC = RC + L_size(1)-index1+1;
            else
                A_sorted(k,1)=L(index1,1);
                index1=index1+1;
            end
        end
    end
end
end